package tianhao.luo.queue;

/**
 * 使用环形数组模拟队列
 * 解决ArrayQueue的缺点:当队列被加满后,再取出数据,再加入数据时,会报错队列已满
 *
 * 思路:
 * 1.front变量的含义调整为:front指向队首的第一个元素,即array[front]就是队列的第一个元素.front初始值为0
 * 2.rear变量的含义调整为:rear指向队列的最后一个元素的后一个位置,需要数组提供一个空闲位,方便我们计算队列是否已满.rear初始值为0
 * 3.当队列已满时,条件为:(rear+1)%maxsize = front;这个条件的来源是:当队列被加满后,再取出数据,再加入数据时,
 * rear的指针已经指向了队列的前面,即rear值小于front了,判断是否满了就要看(rear+1)%maxsize是否与front重合了
 * 取模就是因为要形成环状；rear+1是因为rear位置始终不会存放元素，rear表示队尾的后一个位置，那么环形的队首就是rear+1，即跳过rear
 * 4.当队列为空时,rear==front
 * @author: tianhao.luo@hand-china.com 2021/6/13  15:10
 */
public class CircleArrayQueue {

    /**
     * 队列容量
     */
    private int maxSize;
    /**
     * 队列元素
     */
    private int[] objects;
    /**
     * 队首指针
     */
    private int front;
    /**
     * 队尾指针
     */
    private int rear;


    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        // 初始化队列大小
        this.objects = new int[maxSize];
        // 队列为空时,将队首指向0;
        front = 0;
        // 队列为空时,将队尾指向0;
        rear = 0;
    }


    public boolean isFull(){
        // 取模就是因为要形成环状；
        // rear+1是因为rear位置始终不会存放元素，rear表示队尾的后一个位置，那么环形的队首就是rear+1，即跳过rear
        // 队首 % 数组大小 = 队首
        return (rear+1)%this.maxSize == front;
    }

    public boolean isEmpty(){
        // rear表示队尾的后一个位置，如果它为front，那就表示已经为空了
        return rear == front;
    }
    /**
     * 入队
     * 1.判断对列是否已满
     * 2.未满时,队尾指针后移一位,向队尾插入元素
     * @param i 元素
     */
    public void addQueue(int i){
        if (isFull()){
            throw new RuntimeException("队列已满");
        }
        // rear表示队尾的后一位,当入队时,rear恰好表示的是应该本次入队的元素索引
        objects[rear]=i;
        // 更新rear的值,其值应该为当前入队元素的后一位;为了实现循环,需要进行取模
        rear = (rear+1)% this.maxSize;
    }

    /**
     * 出队
     * 1.判断队列是否为空
     * 2.不为空,队首指针后移一位,取出当前元素
     * @return 队首数据
     */
    public int getQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        // front指向的就是第一个元素
        int value = objects[front];
        // 更新front指向的队首位置,它应该为当前取出元素的后一位;为了循环,需要取模
        front = (++front)%this.maxSize;
        return value;
    }

    /**
     * 展示队首数据
     * @return 队首数据
     */
    public int peek(){
        if (rear == front){
            throw new RuntimeException("队列为空");
        }
        return objects[front];
    }

    /**
     * 展示队列中所有元素
     */
    public void showQueue(){
        if (front == rear){
            System.out.println("队列为空");
            return;
        }
        // i不表示队首的指针,它只是表示有效元素的起始位置.
        // 有效元素的个数为: front 到 front + (rear-front+maxSize)% maxSize
        // 取有效元素时,只需要将有效元素i的位置对maxSize取模
        for (int i = front; i < front+size(); i++) {
            System.out.printf("objects[%d]=%d\n",i%maxSize,objects[i%maxSize]);
        }
    }


    /**
     * 有效长度
     * rear 和front始终不会超过maxSize
     * 第一种情况: rear > front时,有效个数为rear - front
     * 第二种情况: rear < front时,有效个数为(rear -front)+maxSize;这种情况是由于当队列加满元素后,又出列元素,再入队元素导致的
     * 为了让两种情况的值返回结果可以用一个表达式表示,可以对他们取模:
     * 第一种情况: (rear - front) % maxSize
     * 第二种情况: ((rear -front)+maxSize) % maxSize
     * =====>第一种情况也可以为: ((rear - front) % maxSize )+0 ==> ((rear -front)+maxSize) % maxSize
     * 所以可以直接用 ((rear -front)+maxSize) % maxSize表示两种情况
     * @return 有效长度
     */
    public int size(){
        return (rear-front)% maxSize;
    }
}
